/*******************************************************************************
* Lempel Ziv Storer Szymanski (LZSS)
*
* File     : lzss.c
* Autore   : Gianluca Costante
*
********************************************************************************
* AGGIORNAMENTI
*
* 1. 11.10.2011 - Inserita struttura per la terna (flag, offset, length)
* 2. 20.10.2011 - Migliorata ricerca all'interno della finestra di scorrimento
* 3. 23.10.2011 - Inserita scrittura su file di output
* 4. 01.11.2011 - Iniziata la routine per la decompressione
* 5. 20.12.2011 - Inserito passaggio di argomenti da linea di comando
* 6. 20.12.2011 - Aggiornato commenti
* 7. 10.01.2012 - Suddivisione in packages / aggiornato commenti
* 8. 11.01.2012 - Creazione Makefile
*******************************************************************************/

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "bitfile.h"
#include "lzss.h"

/*******************************************************************************
 *   VARIABILI GLOBALI
 ******************************************************************************/
unsigned char window[WINDOW_SIZE];  /* finestra di scorrimento per i simboli */
unsigned char lookahead[MAX_MATCH]; /* buffer dei simboli gia analizzati */

/*******************************************************************************
 *   FUNZIONI
 ******************************************************************************/

/*******************************************************************************
*   Funzione    : EncodeLZSS
*   Descrizione : legge da un file di input i caratteri e li codifica tramite 
*                 l'algoritmo LZSS scrivendo su un file di output il risultato.
* 
*   Parametri   : inFile  - nome del file da analizzare/comprimere
*                 outFile - nome del file dove scrivere il file compresso
*   Ritorna     : Niente
*******************************************************************************/
void EncodeLZSS(char *inFile, char *outFile){

    /* file pointer che rappresenta il file di input */
    FILE *fileIn;
    
    /* bit file pointer che rappresenta il file di ouput */
    bit_file_t *fileOut;

    /* informazioni sulle future corrispondenze all'interno della finestra */
    Match match;
    
    /* variabile usata per salvare temporaneamente il valore di un carattere 
     * appena letto */
    int c;
    
    /* variabile utilizzata per i cicli */
    int i;
    
    /* caratteri presenti nel lookhaead buffer */
    int lookCount;                      
    
    /* posizione dell'ultimo carattere all'interno della finestra e del 
     * lookhaead buffer i valori all'interno della finestra vengono riempiti da 
     * sinistra a destra */
    int lastW, lastL;   

    /* apertura dei file di input e output in modalit� binaria, rispettivamente
     * bit file */
    if ((fileIn = fopen(inFile, "rb")) == NULL){
        
        perror(inFile);
        exit(EXIT_FAILURE);
    }

    if (outFile == NULL){
        
        fileOut = MakeBitFile(stdout, BF_WRITE);
    }
    else{
        
        if ((fileOut = BitFileOpen(outFile, BF_WRITE)) == NULL){
            
            perror(outFile);
            fclose(fileIn);
            exit(EXIT_FAILURE);
        }
    }
    
    /* poiche' si inserisce da sinistra a destra, la testa e' uguale a 0 */
    lastW = 0;
    lastL = 0;

    /***************************************************************************
    * STEP 1:
    * 
    * inizializzazione della finestra di scorrimento con dei valori conosciuti.
    ***************************************************************************/
    for (i = 0; i < WINDOW_SIZE; i++){
        
        window[i] = ' ';
    }

    /***************************************************************************
    * STEP 2:
    * 
    * lettura di una stringa non codificata di lunghezza pari alla lunghezza 
    * massima permessa (MAX_MATCH) per una corrispondenza nella finestra 
    ***************************************************************************/
    for (lookCount = 0; lookCount < MAX_MATCH && (c = getc(fileIn)) != EOF; lookCount++){
        
        lookahead[lookCount] = c;
    }

    /* finche' all'interno del lookhaead buffer ci saranno dei caratteri allora
     * ci sara' qualcosa da analizzare */
    while (lookCount > 0){
        
        /***********************************************************************
        * STEP 3:
        * 
        * cerco una corrispondenza all'interno della finesta
        ***********************************************************************/
        match = FindMatch(lastW, lastL);
        
        /* controllo effettuato per evitare che leggendo gli ultimi caratteri 
         * presenti nel file si trovi una corrispondenza maggiore a quanti sono
         * gli ultimi caratteri letti */
        if (match.length > lookCount){ match.length = lookCount;}

        /***********************************************************************
        * STEP 4:
        * 
        * se la corrispondenza � minore del mininmo consentito, cio� due allora 
        * la lunghezza sar� uno, quindi bisogna codificare con il flag 0, 
        * altrimenti codifichero' con il flag 1
        ***********************************************************************/
        if (match.length <= ONLY_CHAR){
            
            
            /* printf(" => 0 %c\n", lookahead[lastL]); */
            
            /* inserisco un bit e il carattere non codificato all'interno del 
             * file di output */
            BitFilePutBit(UNCODED, fileOut);
            BitFilePutChar(lookahead[lastL], fileOut);
            
            /* la lunghezza sara' quindi 1 */
            match.length = 1;
        }
        else{
            
            /* printf(" => 1 (%d, %d)\n", match.offset, match.length); */
            
            /* la lunghezza e' maggiore del minimo consentito allora scrivo sul
             * file di output offset (12 bit) e length (4 bit) */
            BitFilePutBit(ENCODED, fileOut);
            BitFilePutChar((unsigned char)((match.offset & 0x0FFF) >> 4),fileOut);
            BitFilePutChar((unsigned char)(((match.offset & 0x000F) << 4) | (match.length - (ONLY_CHAR + 1))), fileOut);
        }

        /***********************************************************************
        * STEP 5-6:
        * 
        * sposto un numero di simboli pari alla lunghezza delle corrispondenza 
        * appena trovata dal lookhaead buffer alla finestra e riempio il buffer
        * di altrettanti simboli
        ***********************************************************************/
        i = 0;
        while ((i < match.length) && ((c = getc(fileIn)) != EOF)){
            
            /* rimpiazzo il carattere in testa alla finesta con quello nel buffer */
            window[lastW] = lookahead[lastL];
            
            /* aggiungo il simbolo appena letto al lookahead buffer */
            lookahead[lastL] = c;
            
            /* aggiorno le posizioni di testa, incremento di uno la testa della 
             * finestra, facendo modulo WINDOW_SIZE quando lastW sara' 
             * esattamente all'ultima posizione dell'array corrispondente alla 
             * finestra (cioe' WINDOW_SIZE - 1) se lo si incrementa di uno sfora 
             * perche' un array di WINDOW_SIZE elementi va da 0 a WINDOW_SIZE-1, 
             * con l'introduzione del modulo invece di sforare la testa diventa
             * 0, costruendo cos� una finestra a scorrimento, questo discorso 
             * vale sia per la finestra di che per il lookahead buffer */
            lastW = (lastW + 1) % WINDOW_SIZE;
            lastL = (lastL + 1) % MAX_MATCH;
            i++;
        }

        /* nel caso in cui non ci siano piu' simboli all'interno del file di 
         * input copio solo i caratteri dal lookahead buffer alla finestra e 
         * incremento le posizioni di testa */
        while (i < match.length){
            
            /* rimpiazzo il carattere in testa alla finesta con quello nel 
             * buffer senza piu' aggiornare il buffer */
            window[lastW] = lookahead[lastL];
            
            /* stesso discorso di prima... */
            lastW = (lastW + 1) % WINDOW_SIZE;
            lastL = (lastL + 1) % MAX_MATCH;
            
            /* decremento il contatore di simboli all'interno del buffer, cosi'
             * quando arrivera' a 0 non ci saranno piu' caratteri da analizzare 
             * e la condizione di uscita del while sara' rispettata */
            lookCount--;
            i++;
        }
        
        /***********************************************************************
        * STEP 7:
        * 
        * si ripete dallo STEP 3 finche' tutto il file non e' stato analizzato
        ***********************************************************************/
    }

    /* chiudo i files */
    fclose(fileIn);
    BitFileClose(fileOut);
}

/*******************************************************************************
*   Funzione    : DncodeLZSS
*   Descrizione : legge come input un file codificato e lo decomprime 
* 
*   Parametri   : inFile  - nome del file da analizzare/decomprimere
*                 outFile - nome del file dove scrivere il file deompresso
*   Ritorna     : Niente
*******************************************************************************/
void DecodeLZSS(char *inFile, char *outFile){
    
    /* bit file pointer che rappresenta il file di input */
    bit_file_t *fileIn;
    
    /* file pointer che rappresenta il file di ouput */
    FILE *fileOut;

    /* variabile usata per salvare temporaneamente il valore di un carattere 
     * o di un flag appena letto */
    int c;
    
    /* variabile utilizzata per i cicli */
    int i;
    
    /* indicatore dell'ultimo carattere/simbolo presente nella finestra, come 
     * detto prima l'inserimento in finestra avviene da sinistra a destra */
    int lastW;
    
    /* informazioni sulle corrispondenze all'interno della finestra */
    Match match;              
    
    /* apertura dei file di input e output in modalit� bit file, rispettivamente
     * binaria */
    if ((fileIn = BitFileOpen(inFile, BF_READ)) == NULL){
        
        perror(inFile);
        exit(EXIT_FAILURE);
        return;
    }

    if (outFile == NULL)
    {
        fileOut = stdout;
    }
    else
    {
        if ((fileOut = fopen(outFile, "wb")) == NULL)
        {
            BitFileClose(fileIn);
            perror(outFile);
            exit(EXIT_FAILURE);
        }
    }

    /***************************************************************************
    * STEP 1:
    * 
    * inizializzazione della finestra di scorrimento con dei valori conosciuti.
    ***************************************************************************/
    for (i = 0; i < WINDOW_SIZE; i++){
        
        window[i] = ' ';
    }

    lastW = 0;

    while (1){
        
        /***********************************************************************
        * STEP 2:
        * 
        * lettura del flag di codifica/non codifica
        ***********************************************************************/
        if ((c = BitFileGetBit(fileIn)) == EOF){break;}

        
        /***********************************************************************
        * STEP 3a:
        * 
        * se il flag indica una sequenza non codificata allora devo leggere il 
        * prossimo carattere e scriverlo all'interno del file di output e 
        * metterlo nella finestra
        ***********************************************************************/
        if (c == UNCODED){
            
            /* leggo il prossimo carattere/simbolo */
            if ((c = BitFileGetChar(fileIn)) == EOF){break;}

            /* scrivo il carattre/simobolo nel file di output */
            putc(c, fileOut);
            
            /* inserisco in finestra il simbolo appena letto e scritto */
            window[lastW] = c;
            lastW = (lastW + 1) % WINDOW_SIZE;
        }
        else{
            
            /*******************************************************************
            * STEP 3b:
            * 
            * se invece il flag indica una sequenza codificata allora devo 
            * leggere offset e length, copiare un numero pari a length di 
            * simboli pari a length dalla finestra al file di output, partendo 
            * dalla posizione offset 
            *******************************************************************/
            
            /* prendo offset e lunghezza (16 bit)*/
            if ((match.offset = BitFileGetChar(fileIn)) == EOF){break;}
            if ((match.length = BitFileGetChar(fileIn)) == EOF){break;}

            /* spacchetto offset e length s*/
            match.offset <<= 4;
            match.offset |= ((match.length & 0x00F0) >> 4);
            match.length = (match.length & 0x000F) + ONLY_CHAR + 1;

            /* scrivo partendo, da offset, length simboli nel file di output */
            for (i = 0; i < match.length; i++){
                
                /* prendo il carattere dalla finestra */
                c = window[(match.offset + i) % WINDOW_SIZE];
                
                /* lo scrivo sul file di output */
                putc(c, fileOut);
                
                /* lo copio nel buffer per poter spostare i simboli nella 
                 * finestra */
                lookahead[i] = c;
            }

            /*******************************************************************
            * STEP 4:
            * 
            * copio i simboli della corrispondenza (precedentemente salvati nel
            * buffer) in testa alla finestra, questo per le future 
            * corrispondenze 
            *******************************************************************/
            for (i = 0; i < match.length; i++){
                
                /* copio simbolo nelle varie posizioni, partendo dalla testa */
                window[(lastW + i) % WINDOW_SIZE] = lookahead[i];
            }
            
            /* incremento la testa per averla alla corretta posizione, cioe' il 
             * valore precedente piu' la lunghezza della corrispondenza */
            lastW = (lastW + match.length) % WINDOW_SIZE;
            
            /*******************************************************************
            * STEP 5:
            * 
            * ripeto dallo STEP 2 finche' tutto il file non � stato decompresso
            *******************************************************************/
        }
    }
    
    /* chiudo i files */
    BitFileClose(fileIn);
    fclose(fileOut);
}

/*******************************************************************************
*   Funzione    : FindMatchWithBruteforce
*   Descrizione : cerca all'interno della finestra dei simboli la sequenza piu' 
*                 lunga possibile corrispondente ai simboli contenuti nel buffer 
*                 alttraverso un bruteforce  
* 
*   Parametri   : lastW - posizione dell'ultimo simbolo inserito nella finestra
*                 lastL - posizione dell'ultimo simbolo inserito nel buffer
*   Ritorna     : una struttura che contiene offset e length
*******************************************************************************/
Match FindMatch(int lastW, int lastL){
    
    /* infomazioni sulla corrispondenza */
    Match match = {0, 0};
    
    /* variabile che tiene traccia dell'inizio della corrispondenza */
    int i = lastW;  /* si inizia dal primo simbolo utile nella finestra */
    
    /* contatore per le occorrenze dei simboli */
    int occ = 0;
    
    while(1){
        
        /* cerco la prima corrispondenza */
        if (window[i] == lookahead[lastL]){
            
            /* se sono arrivato qui vuol dire che almeno un carattere c'e' */
            occ = 1;

            /* continuo controlloando i caratteri successivi */
            while(window[(i+occ) % WINDOW_SIZE] == lookahead[(lastL+occ) % MAX_MATCH]){
                
                /* se ho una corrispondenza grande il massimo non ha senso 
                 * andare avanti */
                if (occ >= MAX_MATCH){break;}
                
                /* altrimenti incremento le corrispondenze */
                occ++;
            };

            /* ciclando tutto ogni volta devo controllare che la corrispondenza
             * sia quella di lunghezza massima */
            if (occ > match.length){
                
                match.length = occ;
                match.offset = i;
            }
        }
        
        /* se ho una corrispondenza grande il massimo non ha senso 
         * andare avanti */
        if (occ >= MAX_MATCH){
            match.length = MAX_MATCH;
            break;
        }

        /* aumento la posizione da dove iniziare il controllo sulla 
         * corrispondenza, modulo per far si che scorra... (discorso affrontato
         * in un commento pi� avanti nel codice) */
        i = (i + 1) % WINDOW_SIZE;
        
        /* finche non ho analizzato tutti i caratteri presenti nella finestra */
        if (i == lastW){break;}
    }
    
    return match;
}
